TNotes.leetcode

Appearance

0509. 斐波那契数【简单】

0509. 斐波那契数【简单】 ​

1. 📝 题目描述 ​

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n，请计算 F(n)。

示例 1：

txt
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

txt
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

txt
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

  • 0 <= n <= 30

2. 🎯 s.1 - 递归 ​

js
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (n === 0) return 0
  if (n === 1 || n === 2) return 1
  return fib(n - 1) + fib(n - 2)
}
  • 时间复杂度：O(2n)
  • 空间复杂度：O(n)

3. 🎯 s.2 - 迭代 + 空间优化（推荐） ​

js
/**
 * 计算斐波那契数 F(n)
 * 斐波那契数列定义：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n > 1)
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  // 基础情况直接返回
  if (n <= 1) return n

  // 使用两个变量保存前两个斐波那契数，节省空间
  let prev2 = 0 // F(0)
  let prev1 = 1 // F(1)

  // 从 F(2) 开始迭代计算到 F(n)
  for (let i = 2; i <= n; i++) {
    let current = prev1 + prev2 // F(i) = F(i-1) + F(i-2)
    prev2 = prev1 // 更新前一个数
    prev1 = current // 更新当前数
  }

  return prev1
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

4. 📒 斐波那契数列 ​

  • img

Discussions